package search.eightpuzzle.model;

import java.util.ArrayList;

import java.util.Iterator;
import java.util.List;

public class PuzzleState implements Iterable<PuzzleState> {

    private final byte[][] tiles; // The 9 places (with "empty tile" = 0).

    private final byte[] rowOf; // fast access to the row of a tile

    private final byte[] columnOf; // fast access to the row of a tile

    private final int code; // hash code unique to each state.

    private final PuzzleState parent; // backpointer to predecessor.

    /**
     * Create a new state from scratch.
     */
    public PuzzleState(
            final int tile00, final int tile01, final int tile02,
            final int tile10, final int tile11, final int tile12,
            final int tile20, final int tile21, final int tile22) {
        // Checking if a state is valid
        final boolean[] contained = new boolean[9];
        contained[tile00] = true;
        contained[tile01] = true;
        contained[tile02] = true;
        contained[tile10] = true;
        contained[tile11] = true;
        contained[tile12] = true;
        contained[tile20] = true;
        contained[tile21] = true;
        contained[tile22] = true;
        for (int i = 0; i < 9; ++i) {
            assert contained[i];
        }

        this.tiles = new byte[3][3];
        this.tiles[0][0] = (byte) tile00;
        this.tiles[0][1] = (byte) tile01;
        this.tiles[0][2] = (byte) tile02;
        this.tiles[1][0] = (byte) tile10;
        this.tiles[1][1] = (byte) tile11;
        this.tiles[1][2] = (byte) tile12;
        this.tiles[2][0] = (byte) tile20;
        this.tiles[2][1] = (byte) tile21;
        this.tiles[2][2] = (byte) tile22;

        this.rowOf = new byte[9];
        this.columnOf = new byte[9];
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                this.rowOf[this.tiles[i][j]] = (byte) i;
                this.columnOf[this.tiles[i][j]] = (byte) j;
            }
        }

        this.code = this.calcHashCode();
        this.parent = null;
    }

    /**
     * Create a new state from a parent where some "selectedTile" is moved to the
     * "emptyTile".
     *
     * @param parent
     * @param emptyTileRow
     * @param emptyTileColumn
     * @param selectedTileRow
     * @param selectedTileColumn
     */
    public PuzzleState(
            final PuzzleState parent,
            final int emptyTileRow,
            final int emptyTileColumn,
            final int selectedTileRow,
            final int selectedTileColumn) {
        // Checking if a state is valid
        assert parent.tiles[emptyTileRow][emptyTileColumn] == 0;
        final int rowChange = (emptyTileRow - selectedTileRow) * (emptyTileRow - selectedTileRow);
        final int columnChange = (emptyTileColumn - selectedTileColumn) * (emptyTileColumn - selectedTileColumn);
        assert (rowChange == 0 && columnChange == 1) || (rowChange == 1 && columnChange == 0);

        this.tiles = new byte[3][3];
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                this.tiles[i][j] = parent.tiles[i][j];
            }
        }
        this.rowOf = new byte[9];
        this.columnOf = new byte[9];

        final byte movedTile = this.tiles[selectedTileRow][selectedTileColumn];
        // Move tile
        this.tiles[emptyTileRow][emptyTileColumn] =
                this.tiles[selectedTileRow][selectedTileColumn];
        // Make selected place empty
        this.tiles[selectedTileRow][selectedTileColumn] = 0;

        // Adjust data structures for fast access
        this.rowOf[movedTile] = (byte) emptyTileRow;
        this.columnOf[movedTile] = (byte) emptyTileColumn;
        this.rowOf[0] = (byte) selectedTileRow;
        this.columnOf[0] = (byte) selectedTileColumn;

        // Get hash
        this.code = this.calcHashCode();
        this.parent = parent;
    }

    public boolean hasParent() {
        return this.parent != null;
    }

    public PuzzleState getParent() {
        return this.parent; // or predecessor
    }

    /**
     * Get the tile at this position (0 for no tile).
     */
    public int get(final int row, final int column) {
        return this.tiles[row][column];
    }

    public int getRowOf(final int tile) {
        return this.rowOf[tile];
    }

    public int getColumnOf(final int tile) {
        return this.columnOf[tile];
    }

    /**
     * Get all (up to 4) successors.
     */
    @Override
    public Iterator<PuzzleState> iterator() {
        // find empty tile
        int emptyTileRow = this.rowOf[0];
        int emptyTileColumn = this.columnOf[0];

        final List<PuzzleState> children = new ArrayList<PuzzleState>(4);
        if (emptyTileRow > 0) {
            children.add(new PuzzleState(this,
                    emptyTileRow, emptyTileColumn, emptyTileRow - 1, emptyTileColumn));
        }
        if (emptyTileRow < 2) {
            children.add(new PuzzleState(this,
                    emptyTileRow, emptyTileColumn, emptyTileRow + 1, emptyTileColumn));
        }
        if (emptyTileColumn > 0) {
            children.add(new PuzzleState(this,
                    emptyTileRow, emptyTileColumn, emptyTileRow, emptyTileColumn - 1));
        }
        if (emptyTileColumn < 2) {
            children.add(new PuzzleState(this,
                    emptyTileRow, emptyTileColumn, emptyTileRow, emptyTileColumn + 1));
        }

        return children.iterator();
    }

    /**
     * Precomputed in the constructor: calcHashCode();
     */
    @Override
    public int hashCode() {
        return this.code;
    }

    @Override
    public boolean equals(
            final Object obj) {
        if (obj == null) {
            return false;
        }
        if (obj instanceof PuzzleState) {
            return this.hashCode() == obj.hashCode();
        } else {
            return false;
        }
    }

    @Override
    public String toString() {
        final StringBuilder builder = new StringBuilder(12);
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                builder.append(this.tiles[i][j]);
            }
            if (i < 2) {
                builder.append('/');
            }
        }
        return builder.toString();
    }

    /**
     * Print all states on the way to this state.
     */
    public String printHistory() {
        if (this.hasParent()) {
            final StringBuilder history = new StringBuilder();
            history.append(this.parent.printHistory());
            history.append('\n');
            history.append(this.toString());
            return history.toString();
        } else {
            return this.toString();
        }
    }

    /**
     * Number of moves to reach this state.
     */
    public int getDepth() {
        if (this.hasParent()) {
            return this.parent.getDepth() + 1;
        } else {
            return 0;
        }
    }

    /*
     * For
     * 1 2 3
     * 4 5 6
     * 7 8
     * return 123456780
     */
    private int calcHashCode() {
        int code = 0;
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                code *= 10;
                code += this.tiles[i][j];
            }
        }
        return code;
    }

}
